package org.example.SolutionNew003;

import java.util.*;
import java.util.stream.Collectors;

public class DoubleTree012 {
    public static void main(String[] args) {
        int[] preorder=new int[]{3,9,20,15,7};
        int[] inorder=new int[]{9,3,15,20,7};
        DoubleTree012 dt=new DoubleTree012();
        TreeNode root=dt.buildTree(preorder,inorder);
        System.out.println(root.val);
        System.out.println(root.left.val);
        System.out.println(root.right.val);
        System.out.println(root.right.left.val);
        System.out.println(root.right.right.val);

    }

    //和根节点一样，注意控制两个边界就行了
    Map<Integer,Integer> numMap=new HashMap<>();
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        //从中序中截取数组长度找首节点即可
        for(int i=0;i<inorder.length;i++){
            numMap.put(inorder[i],i);    //快速查找下标
        }
        TreeNode root=subArrayGetOne(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        return root;
    }

    public TreeNode subArrayGetOne(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) {
        if(pre_left>pre_right){
            return null;
        }
        int pre_root=pre_left;
        int in_root=numMap.get(preorder[pre_root]);
        int leftLength=in_root-in_left;
        TreeNode root=new TreeNode(preorder[pre_root]);
        root.left=subArrayGetOne(preorder,inorder,pre_left+1,pre_left+leftLength,in_left,in_root-1);
        root.right=subArrayGetOne(preorder,inorder,pre_left+leftLength+1,pre_right,in_root+1,in_right);
        return root;
    }

    //迭代  其实这个有单调栈的思想了
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode root=new TreeNode(preorder[0]);
        stack.push(root);
        int now=0;
        int index=inorder[now];
        for(int i=1;i<preorder.length;i++){
            int curIndex=preorder[i];
            TreeNode node=new TreeNode(curIndex);
            TreeNode temp=stack.peek();
            if(index!=temp.val){
                temp.left=node;
            }else{
                while(!stack.isEmpty() && index==stack.peek().val){
                    temp=stack.pop();
                    index=inorder[++now];
                }
                temp.right=node;
            }
            stack.push(node);
        }
        return root;
    }


}